package com.zzy.stringorarray;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 380. O(1) 时间插入、删除和获取随机元素
 * 实现RandomizedSet 类：
 * <p>
 * RandomizedSet() 初始化 RandomizedSet 对象
 * bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
 * bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
 * int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
 * 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
 * 输入
 * ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
 * [[], [1], [2], [2], [], [1], [2], []]
 * 输出
 * [null, true, false, true, 2, true, false, 2]
 */
public class L380RandomizedSet {
    int index = -1;//维护最后下标
    int[] nums = new int[200000];
    Map<Integer, Integer> map = new HashMap<>();
    Random random = new Random();

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        map.put(val, ++index);
        nums[index] = val;
        return true;
    }

    public boolean remove(int val) {
        //不存在 返回false
        if (!map.containsKey(val)) {
            return false;
        }
        //获得移除数字的下标
        int location = map.remove(val);
        //移除的不是最后一个，就更新最后一个数的位置，稍后拿这个数覆盖删除数
        if (location != index) {
            map.put(nums[index], location);
        }
        nums[location] = nums[index--];
        return true;
    }

    public int getRandom() {
        return nums[random.nextInt(index + 1)];
    }
}


/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */
